/**
 * @author VernHe
 * @date 2021年07月01日 21:59
 */
public class Solution_0287 {
    public int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 从左向右遍历，让数字回到它应该在的位置上
            while (nums[i] != nums[nums[i] - 1]) {
                // 如果发现这个数应该所处的位置上的数不是它，那么他就与其交换
                swap(i,nums[i] - 1, nums);
            }
            // 上面遍历完之后，可以得到当前位置上的数已经回到了它所处的位置了
            // 如果发现不是，那这个就是重复的数，类似于这种情况3  1  3  2  4
            // 3应该处于第三个，经过上面循环，发现是这样的，继续往后走之前检查一下当前位置
            // 发现不是1，而是3，那么3就是重复的数了
            if (i + 1 != nums[i]) {
                return nums[i];
            }
        }
        // 找不到
        return -1;
    }

    private void swap(int p, int q, int[] nums) {
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    }
}
